#include "../comm.h"
class Solution {
    using PII = pair<int, int>;
private:
    void dijkstra(vector<int>& dist, vector<vector<PII>>& g)
    {
        priority_queue<PII, vector<PII>, greater<PII>> q;
        vector<bool> flag(dist.size());
        dist[0] = 0;
        q.push({0, 0});
        while(q.size())
        {
            auto [top, d] = q.top();
            q.pop();
            if(flag[d] == true) continue;
            flag[d] = true;
            // k: 链接结点 v: 路径长度
            for(auto& [k, v]: g[d])
            {
                if(top + v < dist[k])
                {
                    dist[k] = top + v;
                    q.emplace(top + v, k);
                }
            }
        }
    }
public:
    // 直接暴力枚举每个合法路径，找到最大的值？
    // 利用dijkstra优化，在到达这一点时，先判断走最短路回到0是否时间足够
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<PII>> g(values.size());
        vector<int> dist(n, INT_MAX / 2);
        for(auto v: edges)
        {
            int u = v[0], e = v[1], t = v[2];
            g[u].push_back({e, t});
            g[e].push_back({u, t});
        }

        dijkstra(dist, g);


         int ans = 0;
         vector<int> visit(n);
         auto dfs = [&](auto&& self, int u, int res, int val)
         {
            if(res + dist[u] > maxTime)
                return;
            if(u == 0)
                ans = max(ans, val);
            for(auto& [k, v]: g[u])
            {
                visit[k]++;
                self(self, k, res + v, val + (visit[k] == 1? values[k] : 0));
                visit[k]--;
            }
         };
         visit[0] = 1;
         dfs(dfs, 0, 0, values[0]);
         return ans;

    }
};